package binarysearch;

public class search {
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val=val;
        }
    }
    public TreeNode root;
    //创建二插搜索树
    public  void insert(int key){
     if(root==null) {
         root=new TreeNode(key);
         return;
        }
     TreeNode parent=null;
     TreeNode node=new TreeNode(key);
     TreeNode cur=root;
     while (cur!=null){
         if(key>cur.val){
             parent=cur;
             cur=cur.right;
         } else if(key<cur.val){
             parent=cur;
             cur=cur.left;
         }else {
             return;
         }
     }
    if(parent.val>key){
        parent.left=node;
    }else {
        parent.right=node;
    }
    }
    //查找
    public  TreeNode Find(int val){
        TreeNode cur=root;
     while (cur!=null){
         if(cur.val<val){
             cur=cur.right;
         }else if(cur.val>val){
             cur=cur.left;
         }else {
             return cur;
         }
     }
        return null;
    }
    //删除
    public void remove(int val){
        TreeNode cur=root;
        if(root==null){
            return;
        }
        TreeNode parent=cur;
            if(cur.left==null){
                if(cur.val==val){
                    root=cur.right;
                }else if(cur.right.val==val){
                    parent=cur;
                    parent.right=cur.right;
                }else {
                    parent=cur;
                    parent.left=cur.right;
                }
            }else if(cur.right==null){
                if(cur.val==val){
                    root=cur.left;
                }else if(cur.left.val==val){
                    parent=cur;
                    parent.right=cur.left;
                }else {
                    parent=cur;
                    parent.left=cur.left;
                }
            }else {
             TreeNode tp=cur;
             TreeNode t=cur.right;
             while (t.left!=null){
                 tp=t;
                 t=tp.left;
             }
             cur.val=t.val;
             if(tp.left==t){
                 tp.left=t.right;
             }else {
                 tp.right=t.right;
             }
            }
    }
}
